package org.example.BinaryTree;


import org.example.Tool.Tool;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class ExampleB extends Tool {
    static Binary br = new Binary(1);
    ExampleB(){
        br.left = new Binary(2);
        br.left.left = new Binary(4);
        br.left.right = new Binary(5);
        br.left.right.left = new Binary(7);
        br.right = new Binary(3);
        br.right.left = new Binary(6);
        br.right.right = new Binary(9);
        br.right.left.right = new Binary(8);
    }
    /**
     * 宽度优先遍历
     * @implNote  HashMap
     * */
    public int firstWidthH(Binary br){
        Queue<Binary> qu = new LinkedList<>();
        qu.add(br);
        Map<Binary,Integer> mp = new HashMap<>(); //用来存储节点位置
        mp.put(br,1);
        int index  = 1; //当前的节点位置
        int max = Integer.MIN_VALUE; //最大宽度
        int count =0; //宽度初始值为0
        while (!qu.isEmpty()){
            Binary temp = qu.poll();
            if(index == mp.get(temp)){
                count++;
            }
            else{
                max = Math.max(max,count);
                index++;
                count=1;//初始值为1再结算的时候已经弹出了一个
            }
            //因为队列是先进先出，所以先加左再加右
            if(temp.left!=null){
                qu.add(temp.left);
                mp.put(temp.left,mp.get(temp)+1);
            }
            if(temp.right!=null){
                qu.add(temp.right);
                mp.put(temp.right,mp.get(temp)+1);
            }
        }
        return max;
    }
    /**
     * 宽度优先遍历
     * @implNote 不使用额外的Hashmap
     * */
    public int firstWidthT(Binary br){
        Queue<Binary> qu = new LinkedList<>();
        Binary end = br.right;//记录结束位置为最右边
        Binary current = null;
        int max = Integer.MIN_VALUE;
        int count = 0;
        qu.add(br);
        while(!qu.isEmpty()){
            current = qu.poll();
            if(current==end){
                end = current.right;
                max = Math.max(max,count);
                count=1;
            }
            else{
                count++;
            }
            if(current.left!=null){
                qu.add(current.left);
            }
            if(current.right!=null){
                qu.add(current.right);
            }
        }
        return max;
    }
    public static void main(String[] args) {

        System.out.println(new ExampleB().firstWidthH(br));
        System.out.println(new ExampleB().firstWidthT(br));
    }
}
